package chapter6.huffmantree;

import chapter1.Ex103_ArraySearch_int;

/**
 * Created by lili on 2017/7/1.
 */
//构造Huffman树并获得Huffman编码
//【例6.6】 构造Huffman树并获得Huffman编码。

public class HuffmanTree_example
{
    public static int[] random(int n, int size)            //产生n个随机数，返回整型数组
    {
        if (n<=0)
            return null;                                   //数组变量可获得引用空值
        int values[] = new int[n];                         //动态数组使用new运算符申请数组存储空间
        for (int i=0; i<values.length; i++)                //数组变量通过length属性获得其存储单元数
            values[i] = (int)(Math.random()*size);         //产生一个0～100之间的随机数
        return values;                                     //返回局部变量values要引用的数组
    }

    public static void main(String[] args)
    {
        int[] weight={5,29,7,8,14,23,3,11};              //指定权值集合，例6.6，严书
//      int weight[] = {17,12,5,28,35,3};
//      int weight[] = {7,19,2,6,32,3,21,10};
//        int weight[]={15,23,9,6,30,9,21,10};
//      int weight[] = {23,5,17,4,9,31,29,18};             //09级样卷
//		int weight[] = {13,8,17,24,6,28,18,12};
//      int weight[] = {19,2,13,5,11,7,3,17};              //习题6.38,
//        int weight[] = {19,2,13,5,11,7,3};

//        int weight[] = Ex103_ArraySearch_int.random(8, 30);
        Ex103_ArraySearch_int.print(weight);
        HuffmanTree htree = new HuffmanTree(weight);
        System.out.print(htree.toString());
        String[] code = htree.huffmanCodes();
        System.out.print("Huffman编码:  ");
        for (int i=0; i<code.length; i++)
            System.out.print((char)('A'+i)+"："+code[i]+"  ");
    }
}
/*
//      int weight[] = {23,5,17,4,9,31,29,18};             //09级样卷
Huffman树的结点数组:
第0行 (23, 11, -1, -1)
第1行 (5, 8, -1, -1)
第2行 (17, 10, -1, -1)
第3行 (4, 8, -1, -1)
第4行 (9, 9, -1, -1)
第5行 (31, 12, -1, -1)
第6行 (29, 12, -1, -1)
第7行 (18, 10, -1, -1)
第8行 (9, 9, 3, 1)
第9行 (18, 11, 4, 8)
第10行 (35, 13, 2, 7)
第11行 (41, 13, 9, 0)
第12行 (60, 14, 6, 5)
第13行 (76, 14, 10, 11)
第14行 (136, -1, 12, 13)
Huffman编码:  A：111  B：11011  C：100  D：11010  E：1100  F：01  G：00  H：101

		int weight[] = {13,8,17,24,6,28,18,12};
Huffman树的结点数组:
第0行 (13, 9, -1, -1)
第1行 (8, 8, -1, -1)
第2行 (17, 10, -1, -1)
第3行 (24, 11, -1, -1)
第4行 (6, 8, -1, -1)
第5行 (28, 12, -1, -1)
第6行 (18, 11, -1, -1)
第7行 (12, 9, -1, -1)
第8行 (14, 10, 4, 1)
第9行 (25, 12, 7, 0)
第10行 (31, 13, 8, 2)
第11行 (42, 13, 6, 3)
第12行 (53, 14, 9, 5)
第13行 (73, 14, 10, 11)
第14行 (126, -1, 12, 13)
Huffman编码:  A：001  B：1001  C：101  D：111  E：1000  F：01  G：110  H：000

      int weight[] = {19,2,13,5,11,7,3,17};              //习题6.38
Huffman树的结点数组:
第0行 (19, 13, -1, -1)
第1行 (2, 8, -1, -1)
第2行 (13, 11, -1, -1)
第3行 (5, 9, -1, -1)
第4行 (11, 11, -1, -1)
第5行 (7, 10, -1, -1)
第6行 (3, 8, -1, -1)
第7行 (17, 12, -1, -1)
第8行 (5, 9, 1, 6)
第9行 (10, 10, 3, 8)
第10行 (17, 12, 5, 9)
第11行 (24, 13, 4, 2)
第12行 (34, 14, 7, 10)
第13行 (43, 14, 0, 11)
第14行 (77, -1, 12, 13)
Huffman编码:  A：10  B：01110  C：111  D：0110  E：110  F：010  G：01111  H：00

      int weight[] = {19,2,13,5,11,7,3};
Huffman树的结点数组:
第0行 (19, 11, -1, -1)
第1行 (2, 7, -1, -1)
第2行 (13, 10, -1, -1)
第3行 (5, 8, -1, -1)
第4行 (11, 10, -1, -1)
第5行 (7, 9, -1, -1)
第6行 (3, 7, -1, -1)
第7行 (5, 8, 1, 6)
第8行 (10, 9, 3, 7)
第9行 (17, 11, 5, 8)
第10行 (24, 12, 4, 2)
第11行 (36, 12, 9, 0)
第12行 (60, -1, 10, 11)
Huffman编码:  A：11  B：10110  C：01  D：1010  E：00  F：100  G：10111

//    int weight[]={7,5,1,2};               //严书
    int weight[]={7,5,1,2,1};
 */
/*
int[] weight={5,29,7,8,14,23,3,11};      //指定权值集合，例6.6，严书
Huffman树的结点数组:
第0行 (5, 8, -1, -1)
第1行 (29, 13, -1, -1)
第2行 (7, 9, -1, -1)
第3行 (8, 9, -1, -1)
第4行 (14, 11, -1, -1)
第5行 (23, 12, -1, -1)
第6行 (3, 8, -1, -1)
第7行 (11, 10, -1, -1)
第8行 (8, 10, 6, 0)
第9行 (15, 11, 2, 3)
第10行 (19, 12, 8, 7)
第11行 (29, 13, 4, 9)
第12行 (42, 14, 10, 5)
第13行 (58, 14, 1, 11)
第14行 (100, -1, 12, 13)
Huffman编码:  A：0001  B：10  C：1110  D：1111  E：110  F：01  G：0000  H：001

    int weight[] = {7,19,2,6,32,3,21,10};
Huffman树的结点数组：
第0行  7, 10, -1, -1
第1行  19, 12, -1, -1
第2行  2, 8, -1, -1
第3行  6, 9, -1, -1
第4行  32, 13, -1, -1
第5行  3, 8, -1, -1
第6行  21, 12, -1, -1
第7行  10, 10, -1, -1
第8行  5, 9, 2, 5
第9行  11, 11, 8, 3
第10行  17, 11, 0, 7
第11行  28, 13, 9, 10
第12行  40, 14, 1, 6
第13行  60, 14, 11, 4
第14行  100, -1, 12, 13
Huffman编码：
1010
00
10000
1001
11
10001
01
1011

        int weight[]={15,23,9,6,30,9,21,10};
Huffman树的结点数组:
第0行 (15, 10, -1, -1)
第1行 (23, 12, -1, -1)
第2行 (9, 8, -1, -1)
第3行 (6, 8, -1, -1)
第4行 (30, 12, -1, -1)
第5行 (9, 9, -1, -1)
第6行 (21, 11, -1, -1)
第7行 (10, 9, -1, -1)
第8行 (15, 10, 3, 2)
第9行 (19, 11, 5, 7)
第10行 (30, 13, 0, 8)
第11行 (40, 13, 9, 6)
第12行 (53, 14, 1, 4)
第13行 (70, 14, 10, 11)
第14行 (123, -1, 12, 13)
Huffman编码:  A：100  B：00  C：1011  D：1010  E：01  F：1100  G：111  H：1101


*/

